/*
 * there's also a Suffix Tree method that can find the LCS in O(n+m) time
 */
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <time.h>
#include <algorithm>

void LCS_DP(const char *str1, const char *str2, int *s1, int *s2, int *cn) {
  *s1 = -1;
  *s2 = -1;
  *cn = 0;

  int n = strlen(str1);
  int m = strlen(str2);

  if (n == 0 || m == 0) return;
  int **M = new int*[n+1];
  for (int i = 0; i <= n; ++i) {
    M[i] = new int[m+1];
    memset(M[i], 0, sizeof(int) * (m+1));
  }

  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= m; ++j) {
      if (str1[i-1] == str2[j-1]) M[i][j] = M[i-1][j-1] + 1;
    }
  }

  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= m; ++j) {
      if (M[i][j] > *cn) {
        *cn = M[i][j];
        *s1 = i - *cn;
        *s2 = j - *cn;
      }
    }
  }

  for (int i = 0; i < n; ++i) delete[] M[i];
  delete[] M;
  printf("LCS_DP\n");
}

void LCS_DP_Refined(const char *str1, const char *str2, 
                    int *s1, int *s2, int *cn) {
  *s1 = *s2 = -1;
  *cn = 0;
  int n = strlen(str1);
  int m = strlen(str2);

  if (n == 0 || m == 0) return;

  // NOTE: we can choose the smaller of m and n by swapping the two string
  //       but a longer inner loop is more cache friendly
  int *M = new int[m + 1];
  memset(M, 0, sizeof(int) * (m+1));

  for (int i = 1; i <= n; ++i) {
    for (int j = m; j >= 1; --j) { 
      // NOTE: need to loop from right to left, 
      //       so that the upper-left data is not violated
      if (str1[i-1] == str2[j-1]) {
        M[j] = M[j-1] + 1;
        if (M[j] > *cn) {
          *cn = M[j];
          *s1 = i - *cn;
          *s2 = j - *cn;
        }
      }
      else M[j] = 0;
    }
   /* for (int j = 1; j <= m; ++j) printf("%d ", M[j]);
    printf("\n");*/
  }
  delete[] M;
  printf("LCS_DP refined\n");
}

char RandChar() { return (char)(rand() % 26 + 'A'); }

// we can dictate s1, s2, and cn to specify specific test cases
void GenTwoStrings(char *str1, int n1, char *str2, int n2,
                   int s1, int s2, int cn) {
  printf("%d, %d\n", s1, s2);
  for (int k = 0; k < cn; ++k) {
    str1[s1+k] = str2[s2+k] = RandChar();
  }
  for (int i = 0; i < s1; ++i) str1[i] = RandChar();
  for (int i = s1 + cn; i < n1; ++i) str1[i] = RandChar();
  for (int j = 0; j < s2; ++j) str2[j] = RandChar();
  for (int j = s2 + cn; j < n2; ++j) str2[j] = RandChar();
  str1[n1] = '\0';
  str2[n2] = '\0';
  printf("Gen strings\n");
}
void GenTwoStrings(char *str1, int n1, char *str2, int n2, int cn) {
  int s1 = n1 == cn ? 0 : rand() % (n1 - cn);
  int s2 = n2 == cn ? 0 : rand() % (n2 - cn);
  GenTwoStrings(str1, n1, str2, n2, s1, s2, cn);
}

void Print(const char *str, int s, int n) {
  for (int i = 0; i < n; ++i) printf("%c", str[s+i]);
  printf("\n");
}

void LCSTest() {
  int n1 = rand() % 1000 + 1;
  int n2 = rand() % 1000 + 1;
  char *str1 = new char[n1 + 1];
  char *str2 = new char[n2 + 1];
  int m = rand() % (std::min(n1, n2)) + 1;
  GenTwoStrings(str1, n1, str2, n2, m);
 // printf("%s\n%s\n", str1, str2);
  int s1, s2, cn;
  LCS_DP(str1, str2, &s1, &s2, &cn);
  int s11, s22, cn2;
  LCS_DP_Refined(str1, str2, &s11, &s22, &cn2);
  if (cn < m || cn != cn2 || s1 != s11) {
    printf("---------------------------------------\n");
    Print(str1, s1, cn);
    Print(str2, s2, cn);
    Print(str1, s11, cn2);
    Print(str2, s22, cn2);
  }

  delete[] str1;
  delete[] str2;
}

int main(int argc, const char *argv[]) {
  srand(time(NULL));

  int n_iters = rand() % 50 + 1;
  for (int i = 0; i < n_iters; ++i) {
    LCSTest();
  }
  return 0;
}

